<html>
<head>

<title> Funnycells: CS374, Winter 2010 </title>
</head>

<body>

<h1>
Funnycells assignment: CS 374, Winter 2010
</h1>
<hr>

<p>This is an assignment about funny cells. There are three kinds of cells: susceptible, infected, and antibodies. The infected and antibody cells try to convert their opposite kinds and induct them into their workforce. Students will divide themselves into groups, some groups will program the infected cells, other groups will program the antibody cells, and they will be pitted against each other at the end of the semester! The goal is simple -- for the infected cells it is to infect everybody, and for the antibody cells it is to immunise everybody. But there are some rules:</p>

<ul>

<li><i>Molecular communication</i>: The cells cannot directly talk to one another. They can manufacture molecules and dump these molecules into the medium. The medium is assumed to be sufficiently viscous so that the molecules do not diffuse away. Other cells in the neighborhood can sense these molecules. Note that sensing consumes the molecule, so if a cell has to send some information to two other cells, it has to produce two molecules. Communication can thus happen by producing different kinds of molecules, as long as the different cells know what the information encoded on the molecules means.<br><br></li>

<li><i>Alphabet</i>: The molecules can only use a finite alphabet of <i>a, t, c, g</i> protein sequences. So, any information to be communicated has to be encoded into this 4-letter alphabet.<br><br></li>

<li><i>Energy and lifetime</i>: Molecules have a finite lifetime, and the lifetime depends upon their size. The larger the molecule, the greater its lifetime. But there is also an energy cost to manufacturing molecules -- the larger a molecule, the greater its energy cost. If a cell runs out of energy, it becomes completely ineffective. Energy reservoirs are available, but the cells have to make sure they travel to the reservoirs before they run out of energy since there is energy cost to movement as well.<br><br></li>

<li><i>Quorum</i>: A single cell cannot infect another cell, but a sufficient quorum is required. This is similar to how quorum sensing is necessary in bacterial infections.<br><br></li>

<li><i>Movement</i>: Infected and antibody cells can move around to infect other cells. But since infections can only happen with a sufficient quorum, it is necessary for a group to move together. Or, at least to arrive at target cells at the same time to launch a successful infection.<br></li>

</ul>

This is what it looks like. Susceptible cells are yellow, infected ones are red, and the antibodies are green. The infected cells in my reference implementation also leave pheromone trails, marked with an 'i'. You can see that the infected and antibody cells are moving around in small armies!<br><br>

<img src="mapbefore.png"/>

<br><br>And since the infected cells are smarter, they win at the end!<br><br>

<img src="mapafter.png"/>

<br><br>Although an effort has been made to preserve molecular communication semantics as those available in real cellular networks or projected to happen in futuristic nanonetworks, the mapping is in no way accurate or exhaustive. This is purely meant to serve as an exciting assignment.<br><br>

Before we move to the details, just a note about the different counters reported on the cellular map. The <i>susceptible</i>, <i>infected</i>, and <i>antibody</i> counters give a current count of the number of different types of cells. The <i>infections</i> and <i>immunisations</i> counters give the number of conversions that were made so far. The <i>infected energy</i> and <i>antibody energy</i> counters give an exponentially weighted moving average of the amount of energy consumed per cell per sec by the infected and antibody cells. The <i>infected coord</i> and <i>antibody coord</i> metrics are updated only upon clicking the Update button, and indicate the level of synchrony with which the infected and antibody cells move together. More about the metric later, but this is just to give an indication of whether the cells are able to form groups and move in groups, rather than just moving randomly.<br>

<h2>Running funnycells</h2>

The source code and binaries (compiled on Java 1.6.0_10) for the simulator can be downloaded <a href="funnycells.0.1.tar.gz">here</a>. Note that only binaries are available for my reference implementation of the antibody and infected cells. Instructors can drop me an email for the source code. The code is also available through <a href="http://code.google.com/p/funnycells/source/checkout">SVN on Google Code</a>.<br><br>

The simulator runs in a client-server mode. Each cell runs as a separate Java program, and connects to the server. To run the server, navigate to the funnycells directory and type:<br><br>

<i>java -cp "lib/java-getopt-1.0.13.jar;build" assg.funnycells.server.Coordinator -c [config file] -l [log level] -x [terminate upon infection] -d [display ON/OFF]</i><br>

<blockquote>
-c [config file]: The default file is funnycells.conf, picked up from the current directory. This is explained in more detail later.<br>
-l [log level]: This can be 0 (no logging), 1 (info), or 2 (debug)<br>
-x [terminate upon infection]: This is just a termination condition to end the simulation. If marked as 1, the server will terminate when all susceptible cells have been infected or immunized, ie. the number of susceptible cells goes to zero. 0 indicates that the server will keep running<br>
-v [display ON/OFF]: This can be 0 (no display) or 1 (display active)
</blockquote>

Note that you have to change the ; in the classpath to : depending upon whether you run the command in Linux or Windows or Cygwin.

<br><br>
To create a cell, type:<br><br>

<i>java -cp "lib/java-getopt-1.0.13.jar;build" assg.funnycells.cells.FunnyCell -c [config file] -x [x-coord] -y [y-coord] -t [type] -i [cell-id] -l [log level]</i><br>

<blockquote>
-c [config file]: The configuration file, default being funnycells.conf present in the current directors<br>
-x [x-coord]: The x coordinate at which to create the cell. The top left corner is (0, 0), and the size of the map is defined in funnycells.conf<br>
-y [y-coord]: The y coordinate at which to create the cell<br>
-t [type]: This can be 0 (susceptible cell), 1 (infectious cell), 2 (antibody cell), or 3 (energy cell)<br>
-i [cell-id]: Any string for a cell-id. Each cell has to have a unique id<br>
-l [log-level]: 0 (no logging), 1 (info), or 2 (debug)
</blockquote>

<br>
Alternatively, to create a whole series of cells randomly launched in different squares:<br><br>

<i>perl randomlaunch.pl [map width] [map height] [energy cells] [infected cells] [antibody cells] [susceptible cells]</i><br>

<blockquote>
[map width]: The width of the map, should be the same as that defined in funnycells.conf<br>
[map height]: The vertical length of the map<br>
[energy cells]: The number of energy cells. They are placed at random locations<br>
[infected cells]: The number of infected cells to start with. Placed randomly<br>
[antibody cells]: The number of antibody cells to start with<br>
[susceptible cells]: The number of susceptible cells<br>
</blockquote>

Similarly, to create a lot of cells with the susceptible cells organized in clusters:<br><br>

<i>perl clusterlaunch.pl [map width] [map height] [energy cells] [infected cells] [antibody cells] [susceptible cells] [probability of joining cluster]</i><br><br>

Here, [probability of joining clusters] indicates the probability by which a new susceptible cell will be created in a random location, or next to another susceptible cell. A higher probability will result in a few large clusters, while a smaller probability will result in a lot of small clusters<br><br>


<br>
The maps in the figures above were generated in the scenario <i>randomlaunch.pl 30 30 0 15 15 40</i>, that is on a 30x30 map with no energy reservoirs, 15 infected and antibody cells each, and 40 susceptible cells.<br>

<h4>funnycells.conf</h4>

The configuration file is divided into different sections with the following parameters.<br>

<ul>

<li><i>server</i>: Entries for the IP address and port of the server
<blockquote>
[server]<br>
ip = 127.0.0.1<br>
port = 8080<br>
</blockquote></li>

<li><i>map</i>: Entries for the height and width of the map, and the number of energy cells
<blockquote>
[map]<br>
height = 30<br>
width = 30<br>
numenergy = 10<br>
</blockquote></li>

<li><i>classes</i>: Classes for susceptible and energy cells will be supplied, and students will have to implement their own classes for infected and antibody cells. More on how to implement these classes in described later.
<blockquote>
[classes]<br>
energycell = assg.funnycells.cells.EnergyCellImpl<br>
susceptiblecell = assg.funnycells.cells.SusceptibleCellImpl<br>
infectedcell = assg.funnycells.cells.InfectedCellImpl<br>
antibodycell = assg.funnycells.cells.AntibodyCellImpl<br>
newinfectedcell = assg.funnycells.cells.InfectedCellImpl<br>
newantibodycell = assg.funnycells.cells.AntibodyCellImpl<br>
</blockquote>

Here, the [infectedcell] class is instantiated for infected cells, and the [newinfectedcell] class is instantiated in place of a susceptible of antibody cell which gets infected. Since in the example shown above, both [newinfectedcell] and [infectedcell] are the same, therefore the same class is instantiated in both cases. But different classes can instead be used to simulate interesting effects and distinguish between newly infected cells and the originally infectious cells. For example, if the [newinfectedcell] field is left blank, then newly infected cells actually disappear from the map and do not add to the population to infected cells.<br><br>
</li>

<li><i>receptors</i>: Each molecule that is produced by the cells has to start with a <i>start</i> sequence, end with an <i>end</i> sequence, and has to have receptors for the cell that is meant to sense the molecule. Infected cells can only sense molecules containing the <i>infected</i> sequence, antibody cells can only sense molecules containing the <i>antibody</i> sequence, and any cell (including susceptible cells) can sense molecules containing the <i>any</i> sequence. Thus, a null molecule would be something like <i>gggc-agcg-cccg</i>, consisting of the start sequence, destined for an infected cell, and ending with a valid end sequence. Of course, even null molecules can be used to convey information such as heartbeat status messages!
<blockquote>
[receptors]<br>
start = gggc<br>
stop = cccg<br>
any = atat<br>
infected = agcg<br>
antibody = taca<br>
<blockquote></li>

<li><i>affectors</i>: Cells can define their own affectors, but the following are recognized by the server. <i>Infection</i> and <i>immunisation</i> affectors are used to convert other cells into infected or antibody cells. The <i>presence</i> affector is produced by susceptible cells to signal their presence, and can be sensed by infected and antibody cells that would want to convert it. The <i>energy</i> affector is produced by energy cells, and can be picked up by any cell to gain energy. The <i>pheromone</i> affector is also recognized by the server as having a long lifetime, so that pheromone messages can persist in the network for longer times. Thus, an infection molecule targeted at any cell in the region would be <i>gggc-atat-atga-cccg</i>, composed of the <i>start</i> and <i>end</i> sequences, the <i>any</i> destination, and the <i>infection</i> sequence. Note that infections or immunization molecules affect cells in adjacent squares as well. So, if you dump an infection molecule in (x,y) and another one in (x+1,y+1), they can together cause infections in any of (x,y), (x+1,y), (x,y+1), and (x+1,y+1) squares.

<blockquote>
[affectors]<br>
infection = atga<br>
immunisation = gata<br>
presence = attt<br>
energy = gaag<br>
pheromone = ttta<br>
</blockquote></li>

<li><i>params</i>: A number of control parameters are provided to run the simulation.

<blockquote>
[params]<br>
senseradius = 1: Radius around a cell in which it can sense for molecules. Default of 1 means that the cell can only sense in the rectangle surrounding it.<br>
moltimeout = 100: The time in milliseconds for a molecule of length 1 to expire. Thus, the null molecule mentioned above will expire in 12 times <i>moltimeout</i> duration.<br>
ratetimeout = 5: The maximum rate at which a cell can move is <i>ratetimeout</i> times <i>moltimeout</i>.<br>
droptimeout = 20: The maximum rate which a cell can produce infection or immunisation molecules is <i>droptimeout</i> times <i>moltimeout</i>.<br>
pheromonetimeout = 500: The lifetime of a pheromone molecule is <i>pheromonetimeout</i> times <i>moltimeout</i>.<br>
molenergy = 100: The energy consumed to produce a molecule consisting of only a single letter. Thus, the null molecule explained above will require 12 times <i>molenergy</i> energy<br>
movenergy = 1000: The energy consumed to move one coordinate up or down or left or right or diagonally.<br>
senseenergy = 200: The energy required to sense one molecule.<br>
transferenergy = 10000: The energy supplied by one energy cell.<br>
infectionenergy = 4000: The energy required to produce an infection molecule.<br>
immunisationenergy = 4000: The energy required to produce an immunisation molecule.<br>
maxenergy = 500000: The maximum energy a cell can store, and the energy it starts with.<br>
quorumsize = 2: The quorum size necessary to launch a successful attack or immunisation.<br>
</blockquote></li>


<li><i>colors</i>: <i>color</i> is a misnomer here! Up to three molecules can be listed to be marked in the cellular map on the server. For example, a pheromone molecule for infected nodes starts with <i>gggc-agcg-ttta</i>, and whenever anybody produces this molecule, this will be show on the map marked with an 'i'.
<blockquote>
[colors]<br>
gggcagcgttta = i: For infected pheromones<br>
gggctacattta = a: For antibody pheromones<br>
gggcatatgaag = e: For energy cells<br>
</blockquote></li>

<li><i>display</i>: Defines the window size in pixels for the graphic shown on the server.
<blockquote>
[display]<br>
dispheight = 700<br>
dispwidth = 700<br
</blockqoute></li>


</ul>

<h2>Writing your own infectious and antibody cells</h2>

You will have to implement the <i>InfectedCellImpl</i> and <i>AntibodyCellImpl</i> classes specified in funnycells.conf. The interface that you are provided is very simple. A dummy class will look as follows:<br><br>

public class InfectedCellImpl implements CellularProcesses {
<blockquote>
    public SusceptibleCellImpl(Integer type, Integer energy, String cellId, RateLimBufferedReader in, RateLimPrintWriter out) {<br>
    }<br>
</blockquote>
<blockquote>
public void startCell() {<br>
}<br>
</blockquote>
}<br><br>

The constructor is called with the type of cell (0, 1, 2), the energy you start with, the Id assigned to the cell, and java.io.BufferedReader and java.io.PrintWriter instances for reading and writing messages to communicate with the server. You are only allowed to use the in.readLine() and out.println() methods to receive and send data since these methods have been overridden to limit the rate at which cells can send messages. This is to protect the server from faulty cell implementations that may run into infinite loops because of bugs and cause too many writes on the socket, potentially bringing down the server.<br><br>

If your cell gets taken over by an opponent, it will be destroyed and a new cell with the same cell-id will be created in its place. Note that this will be an instance of the class supplied by your opponent.<br><br>

You can then communicate with the server through the following messages, by writing and reading from the PrintWriter and BufferedReader objects:

<ul>

<li><i>Move</i>

<blockquote>
MOVECELL<br>
incx=[x-offset]<br>
incy=[y-offset]<br>
\n<br>
</blockquote>

Note that you do not know your location! You can only move one cell up or down or left or right or diagonally. Therefore, x-offset and y-offset can be {-1, 0, 1}. The server will respond with one of the following messages:<br>

<blockquote>
OK<br>
MOVECELL<br>
type=[type]<br>
energy=[energy]<br>
\n<br>
</blockquote>

... for a successful move. Your remaining energy will be reported back.<br>

<blockquote>
WALL<br>
Illegal move<br>
\n<br>
</blockquote>

... if you hit a wall.

<blockquote>
ERROR<br>
Not enough energy to move<br>
\n<br>
</blockquote>

... if you run out of energy

<blockquote>
ERROR<br>
Bad arguments in cell move<br>
\n<br>
</blockquote>

... if you sent illegal x and y movement offsets

<blockquote>
ERROR<br>
Malformed MOVECELL message<br>
\n<br>
</blockquote>

... if you sent a bad message<br><br>

</li>

<li><i>Drop molecule</i>

<blockquote>
DROPCHEM<br>
[molecule string]<br>
offx=[x-offset]<br>
offy=[y-offset]<br>
color=[character]<br>
\n<br>
</blockquote>

Here, x-offset and y-offset can be {-1, 0, 1} to drop the molecule at the assigned location. You can also convey a character that the server will display on the network map graphically, but you can do this for at most three colors. Please refer to the funnycells.conf description earlier to read more about this. The server will then respond with one of the following messages:<br>

<blockquote>
OK<br>
DROPCHEM<br>
type=[type]<br>
energy=[energy]<br>
\n<br>
</blockquote>

... for a successful drop.

<blockquote>
ERROR<br>
Malformed chemical<br>
\n<br>
</blockquote>

... if your molecule did not have the appropriate start, drop, and one of {infected, antibody, any} receptors. Please refer to the funnycells.conf explanation earlier.

<blockquote>
ERROR<br>
Rapid infection or antibody drop<br>
\n<br>
</blockquote>

... if you tried to produce infections or immunisations too fast.

<blockquote>
ERROR<br>
Not enough energy to produce chemical<br>
\n<br>
</blockquote>

... if you run out of energy

<blockquote>
ERROR<br>
Bad arguments in drop chemical<br>
\n<br>
</blockquote>

... if you sent illegal x and y movement offsets

<blockquote>
ERROR<br>
Malformed DROPCHEM message<br>
\n<br>
</blockquote>

... if you sent a bad message<br><br>

</li>

<li><i>Sense molecules</i>

<br>
This has two versions: directional and direction-less sensing. With directional sensing, you can specify the x- and y-offsets in which you want to sense. Direction-less sensing checks the entire neigborhood though. The direction-less command is as follows:

<blockquote>
SENSECHEM<br>
[molecule prefix]<br>
max=[maximum to sense]<br>
\n<br>
</blockquote>

You can specify the molecuar prefix for which you want to sense, and the maximum number of molecules that you want to sense for. Remember that if a match is found, the information will be conveyed to you and the molecule will be removed. Sensing consumes molecules it senses for.
<br><br>

The directional sensing command is as follows:

<blockquote>
SENSECHEM<br>
[molecule prefix]<br>
max=[maximum to sense]<br>
offx=[x-offset]<br>
offy=[y-offset]<br>
\n<br>
</blockquote>


The replies are the same for both versions, and will be one of the following messages:<br>

<blockquote>
OK<br>
CHEMICALS=[number of matching molecules]<br>
[molecule string 1]<br>
offx=[x-offset]<br>
offy=[y-offset]<br>
[molecule string 2]<br>
offx=[x-offset]<br>
offy=[y-offset]<br>
...<br>
...<br>
type=[type]<br>
energy=[energy]<br>
\n<br>
</blockquote>

... for a successful sense request. The server returns the number of matching molecules (< max), and details about each molecule including the molecule string, and its x and y offsets. The last two lines report back the remaining energy of the cell, and the type of the cell.

<blockquote>
ERROR<br>
Illegal receptor request<br>
\n<br>
</blockquote>

... if your prefix match for molecules did not have the appropriate start and one of {infected, antibody, any} receptors that you can use. Remember that antibodies can only sense for molecules marked as <i>antibody</i> or <i>any</i>. Please refer to the funnycells.conf explanation earlier.

<blockquote>
ERROR<br>
Not enough energy to sense chemicals<br>
\n<br>
</blockquote>

... if you run out of energy

<blockquote>
ERROR<br>
Sensing out of bounds<br>
\n<br>
</blockquote>

... if you try to do directional sensing outside the grid

<blockquote>
ERROR<br>
Bad arguments in sense chemical<br>
\n<br>
</blockquote>

... if you sent an illegal max request

<blockquote>
ERROR<br>
Malformed SENSECHEM message<br>
\n<br>
</blockquote>

... if you sent a bad message

</li>

</ul>

<h2>Strategy hints</h2>

Let your imagination run wild! There are many ways you can use to improve your performance. For a start, to capture cells you can do a leader election when some cells meet, and the leader can then lead its "army". This is what I do. You will have to think of request-response protocols for leader election, timeouts on when to leave a leader and go searching on your own, and extensive state management to work in cooperation with cells that may be in a completely different state at that time.<br><br>

You can also use pheromone trails to indicate the path to susceptible cells so that your small armies of cells do not wander randomly in search of prey. Alternatively, you can establish a gradient to guide cells to the highest density of pheromones. You may even want to eat up your opponents pheromones for that matter! Try reading up on topics such as ant colonies and swarm intelligence for more ideas.<br><br>

But remember that all these nice tricks come at the cost of energy and time. Your cells may need to replenish their energy periodically, but energy is available at only a few locations in the map. Think about how you can search for energy efficiently, or maybe even designate some cells as explicit energy transfer agents. You can get some ideas by reading up stuff on molecular biology -- how proteins are synthesized and energy is transfered across cells.<br><br>

As you go along, you will also notice that some strateies will work well with certain density of cells, ratio to susceptible cells, and various other parameters. Think how you can make your algorithms dynamic enough to infer the environment and operate accordingly.<br><br>

<h2>Assignments (tentative)</h2>

We will build this step by step:

<ol>

<li>Start with being able to send instructions to the server to move. Your cells should be able to move vertically, horizontally, or diagonally, and reflect off walls. [<a href="assignment1draft2.pdf">Assignment 1</a>]<br><br></li>

<li>Sense and find susceptible cells in the network. How many cells were you able to discover? [<a href="assignment2draft3.pdf">Assignment 2</a>]<br><br></li>

<li>Form groups, explore the network, and infect all susceptible cells. Contrast between search strategies for exploring a random layout of susceptible cells on the map, Vs a clustered layout.[<a href="assignment3draft1.pdf">Assignment 3</a>]<br><br></li>

<li>The Funny Cup begins! Develop strategies for your team and win! Do things like pheromones, swarms, molecule capture, and other interesting operations seen in cells and swarms. [<a href="assignment4draft1.pdf">Assignment 4</a>]<br><br></li>

</ol>

You must document your design choices, protocol, and architecture carefully. Marks will also be assigned based on your code quality, the neatness of your protocol, and the robustness of your state management methods.

<h2>Future enhancements</h2>

We may implement a diffusion process in the substrate at some point. Diffusion can serve as a mechanism for information transfer, for example, to create pheromone gradients, or to modulate the information on the amount and frequency of molecular production that diffuses to other parts of the substrate.

<h2>References</h2>

<ul>

<li><a href="http://www.ece.gatech.edu/research/labs/bwn/nanos/publications.html">Nano networks</a></li>

<li><a href="http://www.ted.com/talks/bonnie_bassler_on_how_bacteria_communicate.html">How bacteria communicate</a></li>

<li><a href="http://en.wikipedia.org/wiki/Ant_colony_optimization">Ant colony optimization</a></li>

<li><a href="http://library.thinkquest.org/27819/guide.shtml#6">How cells work</a></li>

</ul>

</body>
</html>
